<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width">
<meta name="theme-color" content="#222"><meta name="generator" content="Hexo 6.3.0">

  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/favicon.ico">
  <link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.ico">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">



<link rel="stylesheet" href="https://fastly.jsdelivr.net/npm/@fortawesome/fontawesome-free@6.7.2/css/all.min.css" integrity="sha256-dABdfBfUoC8vJUBOwGVdm8L9qlMWaHTIfXt+7GnZCIo=" crossorigin="anonymous">
  <link rel="stylesheet" href="https://fastly.jsdelivr.net/npm/animate.css@3.1.1/animate.min.css" integrity="sha256-PR7ttpcvz8qrF57fur/yAx1qXMFJeJFiA6pSzWi0OIE=" crossorigin="anonymous">

<script class="next-config" data-name="main" type="application/json">{"hostname":"blog.csgrandeur.cn","root":"/","images":"/images","scheme":"Gemini","darkmode":false,"version":"8.22.0","exturl":false,"sidebar":{"position":"left","width_expanded":320,"width_dual_column":240,"display":"post","padding":18,"offset":12},"hljswrap":true,"copycode":{"enable":true,"style":"default"},"fold":{"enable":false,"height":500},"bookmark":{"enable":false,"color":"#222","save":"auto"},"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"stickytabs":false,"motion":{"enable":true,"async":false,"duration":200,"transition":{"menu_item":"fadeInDown","post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"/search.xml","localsearch":{"enable":true,"top_n_per_article":1,"unescape":false,"preload":false,"trigger":"auto"}}</script><script src="/js/config.js"></script>

    <meta name="description" content="20170209  虽然好几年来一直是CSU-OJ的super admin，但是退役后就没怎么管OJ了，都是每年的在役队员在加题。不同人对学校OJ的理解不同，有的当对外交流的窗口，有的只是当一个内部的训练工具，导致部分题目残缺、题号不连续等许多问题。多年不做题也怕手生了挺可惜的，打算业余时间偶尔刷几题，把OJ题目重新整理下，调调字体，补补图之类的，顺便做个完整题解。不知道能不能坚持下去，先挖坑吧">
<meta property="og:type" content="article">
<meta property="og:title" content="CSU-OJ补完计划（一，10xx）">
<meta property="og:url" content="http://blog.csgrandeur.cn/2017-02-09-csu-oj-complete-plan-10xx/index.html">
<meta property="og:site_name" content="CSGrandeur&#39;s Thinking">
<meta property="og:description" content="20170209  虽然好几年来一直是CSU-OJ的super admin，但是退役后就没怎么管OJ了，都是每年的在役队员在加题。不同人对学校OJ的理解不同，有的当对外交流的窗口，有的只是当一个内部的训练工具，导致部分题目残缺、题号不连续等许多问题。多年不做题也怕手生了挺可惜的，打算业余时间偶尔刷几题，把OJ题目重新整理下，调调字体，补补图之类的，顺便做个完整题解。不知道能不能坚持下去，先挖坑吧">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2017-02-09T11:14:14.000Z">
<meta property="article:modified_time" content="2025-03-06T02:27:46.955Z">
<meta property="article:author" content="CSGrandeur">
<meta property="article:tag" content="ACM">
<meta property="article:tag" content="CSU-OJ">
<meta property="article:tag" content="CSUOJ-Complete-plan">
<meta name="twitter:card" content="summary">


<link rel="canonical" href="http://blog.csgrandeur.cn/2017-02-09-csu-oj-complete-plan-10xx/">


<script class="next-config" data-name="page" type="application/json">{"sidebar":"","isHome":false,"isPost":true,"lang":"zh-CN","comments":true,"permalink":"http://blog.csgrandeur.cn/2017-02-09-csu-oj-complete-plan-10xx/","path":"2017-02-09-csu-oj-complete-plan-10xx/","title":"CSU-OJ补完计划（一，10xx）"}</script>

<script class="next-config" data-name="calendar" type="application/json">""</script>
<title>CSU-OJ补完计划（一，10xx） | CSGrandeur's Thinking</title>
  

  <script src="/js/third-party/analytics/baidu-analytics.js"></script>
  <script async src="https://hm.baidu.com/hm.js?7958adf931092425a489778560129144"></script>







  <noscript>
    <link rel="stylesheet" href="/css/noscript.css">
  </noscript>
</head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <div class="column">
      <header class="header" itemscope itemtype="http://schema.org/WPHeader"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏" role="button">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <i class="logo-line"></i>
      <p class="site-title">CSGrandeur's Thinking</p>
      <i class="logo-line"></i>
    </a>
      <p class="site-subtitle" itemprop="description">Cogito Ergo Sum</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger" aria-label="搜索" role="button">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu"><li class="menu-item menu-item-home"><a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a></li><li class="menu-item menu-item-categories"><a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a></li><li class="menu-item menu-item-archives"><a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a></li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
      <div class="search-header">
        <span class="search-icon">
          <i class="fa fa-search"></i>
        </span>
        <div class="search-input-container">
          <input autocomplete="off" autocapitalize="off" maxlength="80"
                placeholder="搜索..." spellcheck="false"
                type="search" class="search-input">
        </div>
        <span class="popup-btn-close" role="button">
          <i class="fa fa-times-circle"></i>
        </span>
      </div>
      <div class="search-result-container">
        <div class="search-result-icon">
          <i class="fa fa-spinner fa-pulse fa-5x"></i>
        </div>
      </div>
    </div>
  </div>

</header>
        
  
  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      <ul class="sidebar-nav">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <div class="sidebar-panel-container">
        <!--noindex-->
        <div class="post-toc-wrap sidebar-panel">
            <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%9C%BA%E5%99%A8%E4%BA%BA%E8%AE%AD%E7%BB%83"><span class="nav-number">1.</span> <span class="nav-text">1015:
机器人训练</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%A5%BF%E6%B9%96%E4%B8%89%E4%BA%BA%E8%A1%8C"><span class="nav-number">2.</span> <span class="nav-text">1014:
西湖三人行</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E7%8B%90%E7%8B%B8%E4%B8%8E%E5%B0%8F%E7%8B%97"><span class="nav-number">3.</span> <span class="nav-text">1013:
狐狸与小狗</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#prestige"><span class="nav-number">4.</span> <span class="nav-text">1012:
Prestige</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#counting-pixels"><span class="nav-number">5.</span> <span class="nav-text">1011:
Counting Pixels</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#water-drinking"><span class="nav-number">6.</span> <span class="nav-text">1010: Water
Drinking</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%8A%9B%E7%A1%AC%E5%B8%81"><span class="nav-number">7.</span> <span class="nav-text">1009:
抛硬币</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#horcrux"><span class="nav-number">8.</span> <span class="nav-text">1008:
Horcrux</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E7%9F%A9%E5%BD%A2%E7%9D%80%E8%89%B2"><span class="nav-number">9.</span> <span class="nav-text">1007:
矩形着色</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#saw"><span class="nav-number">10.</span> <span class="nav-text">1006:
SAW</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#binary-search-tree-analog"><span class="nav-number">11.</span> <span class="nav-text">1005:
Binary Search Tree analog</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#xi-and-bo"><span class="nav-number">12.</span> <span class="nav-text">1004: Xi
and Bo</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#ab-iii"><span class="nav-number">13.</span> <span class="nav-text">1002: A+B
(III)</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#ab-i"><span class="nav-number">14.</span> <span class="nav-text">1000: A+B
(I)</span></a></li></ol></div>
        </div>
        <!--/noindex-->

        <div class="site-overview-wrap sidebar-panel">
          <div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">CSGrandeur</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
        <a href="/archives/">
          <span class="site-state-item-count">72</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
          <a href="/categories/">
        <span class="site-state-item-count">6</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
          <a href="/tags/">
        <span class="site-state-item-count">22</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>

        </div>
      </div>
    </div>

    
  </aside>


    </div>

    <div class="main-inner post posts-expand">


  


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="http://blog.csgrandeur.cn/2017-02-09-csu-oj-complete-plan-10xx/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="CSGrandeur">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="CSGrandeur's Thinking">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="CSU-OJ补完计划（一，10xx） | CSGrandeur's Thinking">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          CSU-OJ补完计划（一，10xx）
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2017-02-09 19:14:14" itemprop="dateCreated datePublished" datetime="2017-02-09T19:14:14+08:00">2017-02-09</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar-check"></i>
      </span>
      <span class="post-meta-item-text">更新于</span>
      <time title="修改时间：2025-03-06 10:27:46" itemprop="dateModified" datetime="2025-03-06T10:27:46+08:00">2025-03-06</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E9%A2%98%E8%A7%A3/" itemprop="url" rel="index"><span itemprop="name">题解</span></a>
        </span>
    </span>

  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody"><blockquote>
<p>20170209</p>
</blockquote>
<p>虽然好几年来一直是CSU-OJ的super
admin，但是退役后就没怎么管OJ了，都是每年的在役队员在加题。不同人对学校OJ的理解不同，有的当对外交流的窗口，有的只是当一个内部的训练工具，导致部分题目残缺、题号不连续等许多问题。多年不做题也怕手生了挺可惜的，打算业余时间偶尔刷几题，把OJ题目重新整理下，调调字体，补补图之类的，顺便做个完整题解。不知道能不能坚持下去，先挖坑吧。</p>
<span id="more"></span>
<blockquote>
<p>20170222</p>
</blockquote>
<p>OJ丑得看不下去了……重做了一个，近期上线吧。</p>
<hr />
<blockquote>
<p>20170307</p>
</blockquote>
<p>OJ、主页、报名系统三个网站合并到一起做了个新网站，已上线。 <a
href="/2017-03-07-csunewoj/">日志留念</a> <a
target="_blank" rel="noopener" href="http://acm.csu.edu.cn/">CSU-ACM Home Page</a></p>
<hr />
<h3 id="机器人训练"><a
target="_blank" rel="noopener" href="http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1015">1015:
机器人训练</a></h3>
<blockquote>
<p>20170316</p>
</blockquote>
<p>把每两个点之间的移动，都分解成一横一竖两个移动，两个移动相互独立，只需要关心移动前后面对的方向，这样思路会清晰许多。</p>
<p>每一步从一个箭头末端去下一个箭头始端，无非都是走一个“L”，只有一个决策不同，先横着还是先竖着，受前后两个箭头方向的影响会有不同的转弯次数。但是不必分类讨论，都走一走试试就好了，只需要调一下分解后的横竖移动的顺序，纯粹模拟即可，稍注意下点重合的情况。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="type">const</span> <span class="type">int</span> TURN_NUM[<span class="number">4</span>][<span class="number">4</span>] =</span><br><span class="line">        &#123;</span><br><span class="line">                &#123;<span class="number">0</span>, <span class="number">2</span>, <span class="number">1</span>, <span class="number">1</span>&#125;,</span><br><span class="line">                &#123;<span class="number">2</span>, <span class="number">0</span>, <span class="number">1</span>, <span class="number">1</span>&#125;,</span><br><span class="line">                &#123;<span class="number">1</span>, <span class="number">1</span>, <span class="number">0</span>, <span class="number">2</span>&#125;,</span><br><span class="line">                &#123;<span class="number">1</span>, <span class="number">1</span>, <span class="number">2</span>, <span class="number">0</span>&#125;</span><br><span class="line">        &#125;;</span><br><span class="line"><span class="comment">//方向压缩到 0:x正，1:x负，2:y正，3:y负</span></span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="type">int</span> <span class="title">Dir</span><span class="params">(<span class="type">int</span> s, <span class="type">int</span> e, <span class="type">int</span> is_y)</span></span>&#123;<span class="keyword">return</span> (e &gt; s) + (is_y &lt;&lt; <span class="number">1</span>);&#125;</span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="type">int</span> <span class="title">ArrowDir</span><span class="params">(<span class="type">int</span> * a)</span></span>&#123;<span class="keyword">return</span> a[<span class="number">0</span>] != a[<span class="number">2</span>] ? <span class="built_in">Dir</span>(a[<span class="number">0</span>], a[<span class="number">2</span>], <span class="number">0</span>) : <span class="built_in">Dir</span>(a[<span class="number">1</span>], a[<span class="number">3</span>], <span class="number">1</span>);&#125;</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">OneStep</span><span class="params">(<span class="type">int</span> s, <span class="type">int</span> e, <span class="type">int</span> is_y, <span class="type">int</span> &amp;turn, <span class="type">int</span> &amp;dir)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(s == e) <span class="keyword">return</span>;</span><br><span class="line">    <span class="type">int</span> nex_dir = <span class="built_in">Dir</span>(s, e, is_y);</span><br><span class="line">    turn += TURN_NUM[dir][nex_dir];</span><br><span class="line">    dir = nex_dir;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">TryOneDir</span><span class="params">(<span class="type">int</span> is_y, <span class="type">int</span> dir, <span class="type">int</span> *now, <span class="type">int</span> *nex)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> turn = <span class="number">0</span>;</span><br><span class="line">    <span class="built_in">OneStep</span>(now[is_y + <span class="number">2</span> ], nex[is_y], is_y, turn, dir);</span><br><span class="line">    <span class="built_in">OneStep</span>(now[!is_y + <span class="number">2</span> ], nex[!is_y], !is_y, turn, dir);</span><br><span class="line">    <span class="built_in">OneStep</span>(nex[<span class="number">0</span>], nex[<span class="number">2</span>], <span class="number">0</span>, turn, dir);</span><br><span class="line">    <span class="built_in">OneStep</span>(nex[<span class="number">1</span>], nex[<span class="number">3</span>], <span class="number">1</span>, turn, dir);</span><br><span class="line">    <span class="keyword">return</span> turn;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> t, n, aw[<span class="number">2</span>][<span class="number">4</span>];</span><br><span class="line">    <span class="keyword">for</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;t); t --; )</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;n);</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; <span class="number">4</span>; i ++) <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;aw[<span class="number">0</span>][i]);</span><br><span class="line">        <span class="type">int</span> now_dir = <span class="built_in">ArrowDir</span>(aw[<span class="number">0</span>]), totalTurn = <span class="number">0</span>, totalDis = <span class="built_in">abs</span>(aw[<span class="number">0</span>][<span class="number">0</span>] - aw[<span class="number">0</span>][<span class="number">2</span>]) + <span class="built_in">abs</span>(aw[<span class="number">0</span>][<span class="number">1</span>] - aw[<span class="number">0</span>][<span class="number">3</span>]);</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; -- n; i ^= <span class="number">1</span>)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">0</span>; j &lt; <span class="number">4</span>; j ++) <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;aw[!i][j]);</span><br><span class="line">            totalTurn += std::<span class="built_in">min</span>(<span class="built_in">TryOneDir</span>(<span class="number">0</span>, now_dir, aw[i], aw[!i]),</span><br><span class="line">                                  <span class="built_in">TryOneDir</span>(<span class="number">1</span>, now_dir, aw[i], aw[!i]));</span><br><span class="line">            now_dir = <span class="built_in">ArrowDir</span>(aw[!i]);</span><br><span class="line">            totalDis += <span class="built_in">abs</span>(aw[i][<span class="number">2</span>] - aw[!i][<span class="number">0</span>]) + <span class="built_in">abs</span>(aw[i][<span class="number">3</span>] - aw[!i][<span class="number">1</span>]) +</span><br><span class="line">                    <span class="built_in">abs</span>(aw[!i][<span class="number">0</span>] - aw[!i][<span class="number">2</span>]) + <span class="built_in">abs</span>(aw[!i][<span class="number">1</span>] - aw[!i][<span class="number">3</span>]);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d %d\n&quot;</span>, totalDis, totalTurn);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="西湖三人行"><a
target="_blank" rel="noopener" href="http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1014">1014:
西湖三人行</a></h3>
<blockquote>
<p>20170316</p>
</blockquote>
<p>先想到的思路是直接DP，<code>dp[cost][status][site]</code>，当前花费、状态（行走、在哪个公交上、在出租上且走了几公里，超过3公里按3公里算）、当前站点，优化的是走的时间。
这个思路的问题是，虽然dp的状态空间是
<code>101*204*100</code>，但是每次更新状态还有<code>100</code>数量级的边遍历，这样就行不通了。然而这个方法却水过去了。</p>
<p>更好的方法状态空间是<code>dp[cost][site]</code>，省去<code>status</code>这一维，需要预处理建图。根据三种交通方式，统一地建成一个点到点的距离+花费的无差别图。</p>
<p>首先是bus，因为公交不会抄近道，如果路线是3-&gt;4-&gt;5，它不会因为3-&gt;6-&gt;5更近就绕道，对bus线路上所有能一次性到达的两点都建一条边。</p>
<p>bus之后，就可以Floyd了，因为走路和出租车都是选最短路走的。Floyd之后对任意两点按直达建边。</p>
<p>这样建图在DP时候不需要考虑“当前状态”，比如出租车，都
<strong>只考虑起点发车</strong> ，如果不是起点发车，
<strong>自然有其他的点建了直达边</strong> 。</p>
<p>如此得到了一个有重边的，每条边有距离、花费两个边权的链式图。接下来就可以DP了。最短路做DP也可以，不过多此一举，干净的DP就好。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;string.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="type">const</span> <span class="type">int</span> maxn = <span class="number">111</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> maxm = <span class="number">30011</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> MAXNUM = <span class="number">0x3f3f3f3f</span>;</span><br><span class="line"><span class="type">int</span> L, N, M, S, T, B;</span><br><span class="line"><span class="type">int</span> hz[maxn][maxn];</span><br><span class="line"><span class="type">int</span> bus[maxn];</span><br><span class="line"><span class="type">int</span> fst[maxn], nex[maxm], v[maxm], w[maxm], cost[maxm];</span><br><span class="line"><span class="type">int</span> ntp;</span><br><span class="line"><span class="type">int</span> dp[<span class="number">105</span>][maxn];</span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="type">void</span> <span class="title">AddEdge</span><span class="params">(<span class="type">int</span> s, <span class="type">int</span> t, <span class="type">int</span> len, <span class="type">int</span> c)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    nex[ntp] = fst[s];</span><br><span class="line">    v[ntp] = t;</span><br><span class="line">    w[ntp] = len;</span><br><span class="line">    cost[ntp] = c;</span><br><span class="line">    fst[s] = ntp ++;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">Floyd</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= N; i ++)</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">1</span>; j &lt;= N; j ++)</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> k = <span class="number">1</span>; k &lt;= N; k ++)</span><br><span class="line">                hz[i][j] = std::<span class="built_in">min</span>(hz[i][k] + hz[k][j], hz[i][j]);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">DPS</span><span class="params">(<span class="type">int</span> costNow, <span class="type">int</span> siteNow)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(costNow &gt; L) <span class="keyword">return</span> MAXNUM;</span><br><span class="line">    <span class="type">int</span> &amp;ans = dp[costNow][siteNow];</span><br><span class="line">    <span class="keyword">if</span>(ans != <span class="number">-1</span>) <span class="keyword">return</span> ans;</span><br><span class="line">    <span class="keyword">if</span>(siteNow == T) <span class="keyword">return</span> ans = <span class="number">0</span>;</span><br><span class="line">    ans = MAXNUM;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = fst[siteNow]; i != <span class="number">-1</span>; i = nex[i])</span><br><span class="line">    &#123;</span><br><span class="line">        ans = std::<span class="built_in">min</span>(ans, <span class="built_in">DPS</span>(costNow + cost[i], v[i]) + w[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> ans;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> t, s, e, len, ans;</span><br><span class="line">    <span class="type">int</span> K;</span><br><span class="line">    <span class="keyword">for</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;t); t --; )</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">memset</span>(fst, <span class="number">-1</span>, <span class="built_in">sizeof</span>(fst));</span><br><span class="line">        <span class="built_in">memset</span>(hz, <span class="number">0x3f</span>, <span class="built_in">sizeof</span>(hz));</span><br><span class="line">        <span class="built_in">memset</span>(dp, <span class="number">-1</span>, <span class="built_in">sizeof</span>(dp));</span><br><span class="line">        ntp = <span class="number">0</span>;</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d%d%d%d%d%d&quot;</span>, &amp;L, &amp;N, &amp;M, &amp;S, &amp;T, &amp;B);</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; M; i ++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">&quot;%d%d%d&quot;</span>, &amp;s, &amp;e, &amp;len);</span><br><span class="line">            hz[s][e] = hz[e][s] = len;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= B; i ++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;K);</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">0</span>; j &lt; K; j ++)</span><br><span class="line">            &#123;</span><br><span class="line">                <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;bus[j]);</span><br><span class="line">                <span class="type">int</span> last = j, tmpLen = <span class="number">0</span>;</span><br><span class="line">                <span class="keyword">for</span>(<span class="type">int</span> k = j - <span class="number">1</span>; k &gt;= <span class="number">0</span>; last = k --)</span><br><span class="line">                &#123;</span><br><span class="line">                    tmpLen += hz[bus[last]][bus[k]];</span><br><span class="line">                    <span class="built_in">AddEdge</span>(bus[k], bus[j], tmpLen * <span class="number">250</span>, <span class="number">6</span>);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">Floyd</span>();</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= N; i ++)</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">1</span>; j &lt;= N; j ++)</span><br><span class="line">            &#123;</span><br><span class="line">                <span class="keyword">if</span>(hz[i][j] != MAXNUM)</span><br><span class="line">                &#123;</span><br><span class="line">                    <span class="built_in">AddEdge</span>(i, j, hz[i][j] * <span class="number">1000</span>, hz[i][j] * <span class="number">3</span>);</span><br><span class="line">                    <span class="built_in">AddEdge</span>(i, j, hz[i][j] * <span class="number">125</span>, <span class="number">10</span> + (hz[i][j] &gt; <span class="number">3</span> ? (hz[i][j] - <span class="number">3</span>) * <span class="number">2</span> : <span class="number">0</span>));</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        ans = <span class="built_in">DPS</span>(<span class="number">0</span>, S);</span><br><span class="line">        <span class="keyword">if</span>(ans == MAXNUM)</span><br><span class="line">            <span class="built_in">printf</span>(<span class="string">&quot;no\n&quot;</span>);</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            <span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, ans);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="狐狸与小狗"><a
target="_blank" rel="noopener" href="http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1013">1013:
狐狸与小狗</a></h3>
<blockquote>
<p>20170314</p>
</blockquote>
<p>一共32个位置，至多<code>C(32, 5) * 5 * 2 = 2013760</code>种状态，基本思路是状态DP，不难想，却难A。当年出题人或许是为了卡map，设置了1秒，我也不乱改时限了，不过还是用<code>unordered_map</code>先水过了一下。
要做到正常时限还是要自己写Hash，Hash写对了，状态随便压缩一下做记忆化搜索基本就能过了。不过还可以有一些“看起来”挺酷的“优化”。</p>
<p>把所有能放的格子编号，就是<code>0~31</code>，表达棋子位置就有三种模式：坐标<code>(x, y)</code>，编号<code>(0~31)</code>，位标记<code>(0, 2, 4, 8 ... 2147483648)</code>，32个位置用位标记需要<code>unsigned int</code>。
棋子走动，其实就是按位左移或右移<code>3~5</code>个位，棋子能不能落下，就是单个棋子的新位置与所有棋子的旧位置按位与一下来判断。一些细节的分类讨论也可以用位运算减少代码量。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;string.h&gt;</span></span></span><br><span class="line"><span class="type">const</span> <span class="type">unsigned</span> LEFT_1357  = <span class="number">0x01010101</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">unsigned</span> RIGHT_2468 = <span class="number">0x80808080</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">unsigned</span> LINE_1357  = <span class="number">0x0F0F0F0F</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">unsigned</span> LINE_2468  = <span class="number">0xF0F0F0F0</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">unsigned</span> TOP_LINE   = <span class="number">0x0000000F</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> maxn = <span class="number">2013761</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> hashSize = <span class="number">1000007</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> pace[<span class="number">4</span>] = &#123;<span class="number">3</span>, <span class="number">4</span>, <span class="number">4</span>, <span class="number">3</span>&#125;;</span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">HashNode</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="type">unsigned</span> dogs, fox;</span><br><span class="line">    <span class="type">int</span> status, m, next;</span><br><span class="line">    <span class="built_in">HashNode</span>()&#123;&#125;</span><br><span class="line">    <span class="built_in">HashNode</span>(<span class="type">unsigned</span> d, <span class="type">unsigned</span> f, <span class="type">int</span> m_, <span class="type">int</span> s, <span class="type">int</span> n)</span><br><span class="line">    :<span class="built_in">dogs</span>(d), <span class="built_in">fox</span>(f), <span class="built_in">m</span>(m_), <span class="built_in">status</span>(s), <span class="built_in">next</span>(n)&#123;&#125;</span><br><span class="line">    <span class="function"><span class="type">bool</span> <span class="title">Vis</span><span class="params">(<span class="type">unsigned</span> dogs_, <span class="type">unsigned</span> fox_, <span class="type">int</span> m_)</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> dogs == dogs_ &amp;&amp; fox == fox_ &amp;&amp; m == m_;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br><span class="line">HashNode hashBuf[maxn];</span><br><span class="line"><span class="type">int</span> hashPointer[hashSize];</span><br><span class="line"><span class="type">int</span> htp = <span class="number">0</span>;</span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="type">int</span> <span class="title">GetHash</span><span class="params">(<span class="type">unsigned</span> dogs, <span class="type">unsigned</span> fox, <span class="type">int</span> m)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> hashNum = ((dogs | fox) % hashSize &lt;&lt; <span class="number">1</span> | m) % hashSize;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = hashPointer[hashNum]; i != <span class="number">-1</span>; i = hashBuf[i].next)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span>(hashBuf[i].<span class="built_in">Vis</span>(dogs, fox, m))</span><br><span class="line">            <span class="keyword">return</span> i;</span><br><span class="line">    &#125;</span><br><span class="line">    hashBuf[htp] = <span class="built_in">HashNode</span>(dogs, fox, m, <span class="number">-1</span>, hashPointer[hashNum]);</span><br><span class="line">    <span class="keyword">return</span> hashPointer[hashNum] = htp ++;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">DPS</span><span class="params">(<span class="type">unsigned</span> dogs, <span class="type">unsigned</span> fox, <span class="type">int</span> m)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="comment">//status == 1表示Dog win， 0表示Fox win，2表示已入栈</span></span><br><span class="line">    <span class="type">int</span> &amp;status = hashBuf[<span class="built_in">GetHash</span>(dogs, fox, m)].status;</span><br><span class="line">    <span class="keyword">if</span>(status != <span class="number">-1</span>)</span><br><span class="line">        <span class="keyword">return</span> status;</span><br><span class="line">    status = <span class="number">2</span>;</span><br><span class="line">    <span class="keyword">if</span>(m == <span class="number">1</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="type">bool</span> moveFlag = <span class="literal">false</span>;</span><br><span class="line">        <span class="type">unsigned</span> tmpdogs = dogs;</span><br><span class="line">        <span class="keyword">while</span>(tmpdogs &gt; <span class="number">0</span>)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="type">unsigned</span> dog = tmpdogs &amp; -tmpdogs;</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> mov = <span class="number">0</span>; mov &lt; <span class="number">2</span>; mov ++)</span><br><span class="line">            &#123;</span><br><span class="line">                <span class="keyword">if</span>(dog &amp; RIGHT_2468 &amp;&amp; mov == <span class="number">1</span> || dog &amp; LEFT_1357 &amp;&amp; mov == <span class="number">0</span>)</span><br><span class="line">                    <span class="keyword">continue</span>;</span><br><span class="line">                <span class="type">unsigned</span> nex = dog &lt;&lt; pace[mov] + !(dog &amp; LINE_1357);</span><br><span class="line">                <span class="keyword">if</span> (nex == <span class="number">0</span> || dogs &amp; nex || fox &amp; nex)</span><br><span class="line">                    <span class="keyword">continue</span>;</span><br><span class="line">                moveFlag = <span class="literal">true</span>;</span><br><span class="line">                <span class="keyword">if</span>(<span class="built_in">DPS</span>(dogs ^ dog ^ nex, fox, !m) == <span class="number">1</span>)</span><br><span class="line">                    <span class="keyword">return</span> status = <span class="number">1</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            tmpdogs &amp;= (tmpdogs - <span class="number">1</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(!moveFlag)</span><br><span class="line">            <span class="keyword">return</span> status = <span class="built_in">DPS</span>(dogs, fox, !m);</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            <span class="keyword">return</span> status = <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span>(fox &amp; TOP_LINE)</span><br><span class="line">            <span class="keyword">return</span> status = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> mov = <span class="number">3</span>; mov &gt;= <span class="number">0</span>; mov --)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span>(fox &amp; RIGHT_2468 &amp;&amp; mov &amp; <span class="number">1</span> || fox &amp; LEFT_1357 &amp;&amp; ~mov &amp; <span class="number">1</span>)</span><br><span class="line">                <span class="keyword">continue</span>;</span><br><span class="line">            <span class="type">unsigned</span> nex;</span><br><span class="line">            <span class="keyword">if</span>(mov &lt; <span class="number">2</span>) nex = fox &lt;&lt; pace[mov] + !(fox &amp; LINE_1357);</span><br><span class="line">            <span class="keyword">else</span> nex = fox &gt;&gt; pace[mov] + !(fox &amp; LINE_2468);</span><br><span class="line">            <span class="keyword">if</span> (nex == <span class="number">0</span> || dogs &amp; nex)</span><br><span class="line">                <span class="keyword">continue</span>;</span><br><span class="line">            <span class="keyword">if</span> (<span class="built_in">DPS</span>(dogs, nex, !m) == <span class="number">0</span>)</span><br><span class="line">                <span class="keyword">return</span> status = <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> status = <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> t, m, x, y;</span><br><span class="line">    <span class="type">unsigned</span> dogs, fox;</span><br><span class="line">    <span class="built_in">memset</span>(hashPointer, <span class="number">-1</span>, <span class="built_in">sizeof</span>(hashPointer));</span><br><span class="line">    <span class="keyword">for</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;t); t --; )</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;m);</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>, &amp;x, &amp;y);</span><br><span class="line">        fox = <span class="number">1u</span> &lt;&lt; ((x - <span class="number">1</span>) &lt;&lt; <span class="number">2</span> | (y - <span class="number">1</span>) &gt;&gt; <span class="number">1</span>);</span><br><span class="line">        dogs = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; <span class="number">4</span>; i ++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>, &amp;x, &amp;y);</span><br><span class="line">            dogs |= <span class="number">1u</span> &lt;&lt; ((x - <span class="number">1</span>) &lt;&lt; <span class="number">2</span> | (y - <span class="number">1</span>) &gt;&gt; <span class="number">1</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%s\n&quot;</span>, <span class="built_in">DPS</span>(dogs, fox, m) ? <span class="string">&quot;Dog win&quot;</span> : <span class="string">&quot;Fox win&quot;</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="prestige"><a
target="_blank" rel="noopener" href="http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1012">1012:
Prestige</a></h3>
<blockquote>
<p>20170313</p>
</blockquote>
<p>首先理解题意是两个人都要争取自己拿到的多，在这个前提下让对方也拿到的多。优先拿对自己价值高的，等价情况下优先拿走对对方价值低的（把等价情况下对对方价值高的留给对方），这个思路是对的，也即Han也会用这个思路拿，但需要一个全局策略，即求一个全局的尽可能按上面思路拿的策略。</p>
<p>题目数据规模不允许进行全局状态的DP（比如位运算什么的），那么只能用一个调整的策略。</p>
<p>Li的策略比较直白，所以先按Li取的优先级排序，然后游戏开始。</p>
<p>考虑第<code>i</code>个物品，轮到Han，则假设直接取，但做记录，轮到Li，则看物品<code>i</code>对于已假设Han取了的物品集合而言，是否比这个集合中对Han价值最差的（对Han价值尽可能低，对Li价值尽可能高）物品<code>x</code>，要价值更好，如果更好，那么“时光倒流”，当Han面对物品<code>x</code>的时候，取<code>i</code>，因为已经排序，所以“当时”如果取了<code>i</code>，Li肯定会取<code>x</code>。</p>
<p>不断这样进行下去，这个假设的集合最终就是Han的策略会取的物品集合。</p>
<p>需要Log(n)来找到这个<code>x</code>，用一个优先级队列。
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">typedef</span> pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt; pii;</span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">cmp</span> &#123; ;</span><br><span class="line">    <span class="function"><span class="type">bool</span> <span class="title">operator</span><span class="params">()</span><span class="params">(<span class="type">const</span> pii &amp;a, <span class="type">const</span> pii &amp;b)</span> <span class="type">const</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> a.first != b.first ? a.first &gt; b.first : a.second &lt; b.second;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> t, n, l, h;</span><br><span class="line">    <span class="type">char</span> start[<span class="number">10</span>];</span><br><span class="line">    <span class="keyword">for</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;t); t --; )</span><br><span class="line">    &#123;</span><br><span class="line">        priority_queue&lt;pii, vector&lt;pii&gt;, cmp&gt; H;</span><br><span class="line">        <span class="type">int</span> ansl = <span class="number">0</span>, ansh = <span class="number">0</span>;</span><br><span class="line">        vector&lt;pii&gt; L;</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d%s&quot;</span>, &amp;n, start);</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; n; i ++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>, &amp;l, &amp;h);</span><br><span class="line">            L.<span class="built_in">push_back</span>(<span class="built_in">pii</span>(l, h));</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">sort</span>(L.<span class="built_in">begin</span>(), L.<span class="built_in">end</span>(), <span class="built_in">cmp</span>());</span><br><span class="line">        <span class="keyword">if</span>(start[<span class="number">0</span>] == <span class="string">&#x27;L&#x27;</span>)</span><br><span class="line">            ansl += L[<span class="number">0</span>].first;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> isH = <span class="number">1</span>, i = start[<span class="number">0</span>] == <span class="string">&#x27;L&#x27;</span>; i &lt; L.<span class="built_in">size</span>(); isH ^= <span class="number">1</span>, i ++)</span><br><span class="line">        &#123;</span><br><span class="line">            pii &amp;now = L[i];</span><br><span class="line">            <span class="keyword">if</span>(isH)</span><br><span class="line">            &#123;</span><br><span class="line">                ansh += now.second;</span><br><span class="line">                H.<span class="built_in">push</span>(<span class="built_in">pii</span>(now.second, now.first));</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">            &#123;</span><br><span class="line">                <span class="keyword">if</span>(!<span class="built_in">cmp</span>()(<span class="built_in">pii</span>(now.second, now.first), H.<span class="built_in">top</span>()))</span><br><span class="line">                    ansl += now.first;</span><br><span class="line">                <span class="keyword">else</span></span><br><span class="line">                &#123;</span><br><span class="line">                    ansl += H.<span class="built_in">top</span>().second;</span><br><span class="line">                    ansh -= H.<span class="built_in">top</span>().first;</span><br><span class="line">                    ansh += now.second;</span><br><span class="line">                    H.<span class="built_in">pop</span>();</span><br><span class="line">                    H.<span class="built_in">push</span>(<span class="built_in">pii</span>(now.second, now.first));</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d %d\n&quot;</span>, ansl, ansh);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h3 id="counting-pixels"><a
target="_blank" rel="noopener" href="http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1011">1011:
Counting Pixels</a></h3>
<blockquote>
<p>20170313</p>
</blockquote>
<p>只与半径有关，考虑右上的四分之一圆最后乘 4
即可。半径是整数，把这四分之一圆圈住的像素看作一列一列，圆与每列左边界的交点向上取整就是这一列的像素数，加起来。
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;math.h&gt;</span></span></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">long</span> <span class="type">long</span> x, y, r;</span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%lld%lld%lld&quot;</span>, &amp;x, &amp;y, &amp;r) &amp;&amp; (x || y || r))</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="type">long</span> <span class="type">long</span> ans = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">long</span> <span class="type">long</span> i = <span class="number">0</span>; i &lt; r; i ++)</span><br><span class="line">        &#123;</span><br><span class="line">            ans += (<span class="type">long</span> <span class="type">long</span>)(<span class="built_in">ceil</span>(<span class="built_in">sqrt</span>(r * r - i * i)) + <span class="number">1e-8</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%lld\n&quot;</span>, ans * <span class="number">4</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h3 id="water-drinking"><a
target="_blank" rel="noopener" href="http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1010">1010: Water
Drinking</a></h3>
<blockquote>
<p>20170222</p>
</blockquote>
<p>很稀疏的图，记录父子节点关系最后枚举迭代一下就好。不过其实是个食物链并查集模型，比基本并查集多维护一个与父节点的距离。
已经忘了食物链怎么写了，于是复习一下。。。其实还是瞎写的。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="type">int</span> p[<span class="number">100011</span>];</span><br><span class="line"><span class="type">int</span> dis[<span class="number">100011</span>];</span><br><span class="line"><span class="type">bool</span> s[<span class="number">100011</span>];</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">fa</span><span class="params">(<span class="type">int</span> x)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(x == p[x]) <span class="keyword">return</span> x;</span><br><span class="line">    <span class="built_in">fa</span>(p[x]);</span><br><span class="line">    dis[x] += dis[p[x]];</span><br><span class="line">    p[x] = <span class="built_in">fa</span>(p[x]);</span><br><span class="line">    <span class="keyword">return</span> p[x];</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> n, a, b;</span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;n) != EOF)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt;= n; i ++)</span><br><span class="line">            p[i] = i, dis[i] = <span class="number">0</span>, s[i] = <span class="literal">false</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; n; i ++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>, &amp;a, &amp;b);</span><br><span class="line">            s[a] = <span class="literal">true</span>;</span><br><span class="line">            p[b] = a;</span><br><span class="line">            dis[b] = <span class="number">1</span>;</span><br><span class="line">            <span class="built_in">fa</span>(b);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="type">int</span> ans = <span class="number">-1</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i ++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="built_in">fa</span>(i);</span><br><span class="line">            <span class="keyword">if</span> (!s[i] &amp;&amp; (ans == <span class="number">-1</span> || dis[i] &lt; dis[ans]))</span><br><span class="line">                ans = i;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, ans);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="抛硬币"><a
target="_blank" rel="noopener" href="http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1009">1009:
抛硬币</a></h3>
<blockquote>
<p>20170222</p>
</blockquote>
<p>对每列排序，大的跟大的乘，小的很小的乘，最后加起来总期望最高。 证明：
设<code>a&gt;c, b&gt;d</code>,
<code>(ab+cd) - (ad + bc) = (a - c)*(b - d) &gt; 0</code>，即假设已排好序，这时调换任意两个数的位置，得到的结果会小于先前。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="type">double</span> p[<span class="number">11</span>][<span class="number">111</span>];</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> n, m;</span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>, &amp;n, &amp;m) &amp;&amp; n &amp;&amp; m)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; n; i ++)</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">0</span>; j &lt; m; j ++)</span><br><span class="line">                <span class="built_in">scanf</span>(<span class="string">&quot;%lf&quot;</span>, &amp;p[j][i]);</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">0</span>; j &lt; m; j ++)</span><br><span class="line">            std::<span class="built_in">sort</span>(p[j], p[j] + n);</span><br><span class="line">        <span class="type">double</span> ret = <span class="number">0</span>, tmp;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; n; i ++)</span><br><span class="line">        &#123;</span><br><span class="line">            tmp = <span class="number">1</span>;</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">0</span>; j &lt; m; j ++)</span><br><span class="line">                tmp *= p[j][i];</span><br><span class="line">            ret += tmp;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%.4f\n&quot;</span>, ret);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<h3 id="horcrux"><a
target="_blank" rel="noopener" href="http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1008">1008:
Horcrux</a></h3>
<blockquote>
<p>20170222</p>
</blockquote>
<p>用栈的结构，每段连续相同颜色的第一个的位置为栈元素，每次变色，相当于最后一段连续颜色的起点变成了当前起点的上一个，也即出栈操作。过程中控制好颜色标记。
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stack&gt;</span></span></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> n, horcrux, nowcolor;</span><br><span class="line">    std::stack&lt;<span class="type">int</span>&gt; s;</span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;n) != EOF)</span><br><span class="line">    &#123;</span><br><span class="line">        nowcolor = <span class="number">-1</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i ++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;horcrux);</span><br><span class="line">            <span class="keyword">if</span>(s.<span class="built_in">empty</span>() || horcrux != nowcolor &amp;&amp; (i &amp; <span class="number">1</span>))</span><br><span class="line">            &#123;</span><br><span class="line">                s.<span class="built_in">push</span>(i);</span><br><span class="line">                nowcolor = horcrux;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span> <span class="keyword">if</span>(horcrux != nowcolor)</span><br><span class="line">            &#123;</span><br><span class="line">                nowcolor = horcrux;</span><br><span class="line">                <span class="keyword">if</span>(s.<span class="built_in">size</span>() &gt; <span class="number">1</span>) s.<span class="built_in">pop</span>();</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="type">int</span> ans = <span class="number">0</span>, right = n + <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">while</span>(!s.<span class="built_in">empty</span>())</span><br><span class="line">        &#123;</span><br><span class="line">            ans += (!nowcolor) * (right - s.<span class="built_in">top</span>());</span><br><span class="line">            nowcolor = !nowcolor;</span><br><span class="line">            right = s.<span class="built_in">top</span>();</span><br><span class="line">            s.<span class="built_in">pop</span>();</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, ans);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h3 id="矩形着色"><a
target="_blank" rel="noopener" href="http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1007">1007:
矩形着色</a></h3>
<blockquote>
<p>20170222</p>
</blockquote>
<p>把情况想清楚就好。 <figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> t;</span><br><span class="line">    <span class="type">int</span> px, py, ax, ay, bx, by;</span><br><span class="line">    <span class="keyword">for</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;t); t --; )</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d%d%d%d%d%d&quot;</span>, &amp;px, &amp;py, &amp;ax, &amp;ay, &amp;bx, &amp;by);</span><br><span class="line">        <span class="keyword">if</span>(px &lt; ax || px &gt; bx || py &lt; ay || py &gt; by)</span><br><span class="line">            <span class="built_in">printf</span>(<span class="string">&quot;Outside\n&quot;</span>);</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span>(px == ax || px == bx || py == ay || py == by)</span><br><span class="line">            <span class="built_in">printf</span>(<span class="string">&quot;On\n&quot;</span>);</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            <span class="built_in">printf</span>(<span class="string">&quot;Inside\n&quot;</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h3 id="saw"><a
target="_blank" rel="noopener" href="http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1006">1006:
SAW</a></h3>
<blockquote>
<p>20170222</p>
</blockquote>
<p>当年校队的大大们给新人开的一个小玩笑。当时还没看过《电锯惊魂》，都没理解标题的SAW是什么意思。
题目就是随机一个大写的26个英文字母之一，随机也好固定一个字母押宝也好，过的概率是一样的。</p>
<p>但是前些天看到有个代码100%
AC，还以为spj坏了，看了一下spj的代码，原来是当年随机字母就用的srand(time(0))做种子，提交的代码也这样，而提交代码与spj代码运行时间很近，两个种子就一样了。</p>
<p>于是我邪恶地把spj的随机过程搞得更乱了 😂。 <figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;A&quot;</span>);</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h3 id="binary-search-tree-analog"><a
target="_blank" rel="noopener" href="http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1005">1005:
Binary Search Tree analog</a></h3>
<blockquote>
<p>20170222</p>
</blockquote>
<p>二叉搜索树基础 <figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">Node</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="type">int</span> num;</span><br><span class="line">    <span class="type">int</span> left;</span><br><span class="line">    <span class="type">int</span> right;</span><br><span class="line">    <span class="built_in">Node</span>()&#123;left = right = num = <span class="number">-1</span>;&#125;</span><br><span class="line">&#125;;</span><br><span class="line">Node nd[<span class="number">1111</span>];</span><br><span class="line"><span class="type">int</span> ltp;</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">Insert</span><span class="params">(<span class="type">int</span> x, <span class="type">int</span> now)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(nd[now].num == <span class="number">-1</span>)</span><br><span class="line">        nd[now].num = x;</span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">if</span>(nd[now].num &gt; x)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span>(nd[now].left == <span class="number">-1</span>)</span><br><span class="line">            nd[ltp] = <span class="built_in">Node</span>(), nd[now].left = ltp ++;</span><br><span class="line">        <span class="built_in">Insert</span>(x, nd[now].left);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span>(nd[now].right == <span class="number">-1</span>)</span><br><span class="line">            nd[ltp] = <span class="built_in">Node</span>(), nd[now].right = ltp ++;</span><br><span class="line">        <span class="built_in">Insert</span>(x, nd[now].right);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="type">bool</span> printed;</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">PrintTree</span><span class="params">(<span class="type">int</span> now, <span class="type">int</span> order)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(order == <span class="number">1</span>)</span><br><span class="line">        <span class="built_in">printf</span>(printed ? <span class="string">&quot; %d&quot;</span> : <span class="string">&quot;%d&quot;</span>, nd[now].num), printed = <span class="literal">true</span>;</span><br><span class="line">    <span class="keyword">if</span>(nd[now].left != <span class="number">-1</span>)</span><br><span class="line">        <span class="built_in">PrintTree</span>(nd[now].left, order);</span><br><span class="line">    <span class="keyword">if</span>(order == <span class="number">2</span>)</span><br><span class="line">        <span class="built_in">printf</span>(printed ? <span class="string">&quot; %d&quot;</span> : <span class="string">&quot;%d&quot;</span>, nd[now].num), printed = <span class="literal">true</span>;</span><br><span class="line">    <span class="keyword">if</span>(nd[now].right != <span class="number">-1</span>)</span><br><span class="line">        <span class="built_in">PrintTree</span>(nd[now].right, order);</span><br><span class="line">    <span class="keyword">if</span>(order == <span class="number">3</span>)</span><br><span class="line">        <span class="built_in">printf</span>(printed ? <span class="string">&quot; %d&quot;</span> : <span class="string">&quot;%d&quot;</span>, nd[now].num), printed = <span class="literal">true</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> t, n;</span><br><span class="line">    <span class="keyword">for</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;t); t --; )</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;n);</span><br><span class="line">        ltp = <span class="number">0</span>;</span><br><span class="line">        nd[ltp ++] = <span class="built_in">Node</span>();</span><br><span class="line">        <span class="type">int</span> x;</span><br><span class="line">        <span class="keyword">while</span>(n --)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;x);</span><br><span class="line">            <span class="built_in">Insert</span>(x, <span class="number">0</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        printed = <span class="literal">false</span>; <span class="built_in">PrintTree</span>(<span class="number">0</span>, <span class="number">1</span>); <span class="built_in">printf</span>(<span class="string">&quot;\n&quot;</span>);</span><br><span class="line">        printed = <span class="literal">false</span>; <span class="built_in">PrintTree</span>(<span class="number">0</span>, <span class="number">2</span>); <span class="built_in">printf</span>(<span class="string">&quot;\n&quot;</span>);</span><br><span class="line">        printed = <span class="literal">false</span>; <span class="built_in">PrintTree</span>(<span class="number">0</span>, <span class="number">3</span>); <span class="built_in">printf</span>(<span class="string">&quot;\n&quot;</span>);</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;\n&quot;</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h3 id="xi-and-bo"><a
target="_blank" rel="noopener" href="http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1004">1004: Xi
and Bo</a></h3>
<blockquote>
<p>20170222</p>
</blockquote>
<p>用并查集合并相连的站点。 <figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="type">int</span> p[<span class="number">111</span>];</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">fa</span><span class="params">(<span class="type">int</span> x)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> x == p[x] ? x : (p[x] = <span class="built_in">fa</span>(p[x]));</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> t, n, m, start, end;</span><br><span class="line">    <span class="keyword">for</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;t); t --; )</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>, &amp;start, &amp;end);</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;n);</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt;= <span class="number">100</span>; i ++)</span><br><span class="line">            p[i] = i;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; n; i ++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;m);</span><br><span class="line">            <span class="type">int</span> first = <span class="number">-1</span>, connected;</span><br><span class="line">            <span class="keyword">while</span>(m --)</span><br><span class="line">            &#123;</span><br><span class="line">                <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;connected);</span><br><span class="line">                <span class="keyword">if</span>(first == <span class="number">-1</span>)</span><br><span class="line">                    first = connected;</span><br><span class="line">                <span class="keyword">else</span></span><br><span class="line">                    p[<span class="built_in">fa</span>(connected)] = <span class="built_in">fa</span>(first);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%s\n&quot;</span>, <span class="built_in">fa</span>(start) == <span class="built_in">fa</span>(end) ? <span class="string">&quot;Yes&quot;</span> : <span class="string">&quot;No&quot;</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure> ### <a
target="_blank" rel="noopener" href="http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1003">1003: UC
Browser</a> &gt; 20170222</p>
<p>按题意做。 <figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> t, n;</span><br><span class="line">    <span class="type">char</span> buf[<span class="number">111</span>];</span><br><span class="line">    <span class="keyword">for</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;t); t --; )</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="type">int</span> score = <span class="number">0</span>, tmpscore = <span class="number">0</span>;</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d%s&quot;</span>, &amp;n, buf);</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt;= n; i ++)</span><br><span class="line">        &#123;</span><br><span class="line">            buf[i] == <span class="string">&#x27;1&#x27;</span> ? tmpscore ++ : (tmpscore = <span class="number">0</span>);</span><br><span class="line">            score += <span class="number">10</span> * ((tmpscore - <span class="number">1</span>) % <span class="number">5</span> + <span class="number">1</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="type">int</span> level = (score + <span class="number">50</span>) / <span class="number">100</span>;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, level &gt; <span class="number">8</span> ? <span class="number">8</span> : level);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h3 id="ab-iii"><a
target="_blank" rel="noopener" href="http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1002">1002: A+B
(III)</a></h3>
<blockquote>
<p>20170209</p>
</blockquote>
<p>int64基础知识。CSU-OJ是Linux编译器，用long long <figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;string.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">long</span> <span class="type">long</span> a, b;</span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%lld%lld&quot;</span>, &amp;a, &amp;b) &amp;&amp; a &amp;&amp; b)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%lld\n&quot;</span>, a + b);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure> ### <a
target="_blank" rel="noopener" href="http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1001">1001: A+B
(II)</a> &gt; 20170209</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;string.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">double</span> a, b;</span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%lf%lf&quot;</span>, &amp;a, &amp;b) != EOF)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%.4f\n&quot;</span>, a + b);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="ab-i"><a
target="_blank" rel="noopener" href="http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1000">1000: A+B
(I)</a></h3>
<blockquote>
<p>20170209</p>
</blockquote>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;string.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> a, b;</span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>, &amp;a, &amp;b) != EOF)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, a + b);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

    </div>

    
    
    

    <footer class="post-footer">
          <div class="post-tags">
              <a href="/tags/ACM/" rel="tag"># ACM</a>
              <a href="/tags/CSU-OJ/" rel="tag"># CSU-OJ</a>
              <a href="/tags/CSUOJ-Complete-plan/" rel="tag"># CSUOJ-Complete-plan</a>
          </div>

        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/2016-10-18-again-the-social-network/" rel="prev" title="二刷《社交网络》">
                  <i class="fa fa-angle-left"></i> 二刷《社交网络》
                </a>
            </div>
            <div class="post-nav-item">
                <a href="/2017-03-07-csunewoj/" rel="next" title="CSU-ACM新官网上线">
                  CSU-ACM新官网上线 <i class="fa fa-angle-right"></i>
                </a>
            </div>
          </div>
    </footer>
  </article>
</div>






    <div class="comments utterances-container"></div>
</div>
  </main>

  <footer class="footer">
    <div class="footer-inner">

  <div class="copyright">
    &copy; 
    <span itemprop="copyrightYear">2025</span>
    <span class="with-love">
      <i class="fa fa-heart"></i>
    </span>
    <span class="author" itemprop="copyrightHolder">CSGrandeur</span>
  </div>
  <div class="powered-by">由 <a href="https://hexo.io/" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/" rel="noopener" target="_blank">NexT.Gemini</a> 强力驱动
  </div>

    </div>
  </footer>

  
  <div class="toggle sidebar-toggle" role="button">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>
  <div class="sidebar-dimmer"></div>
  <div class="back-to-top" role="button" aria-label="返回顶部">
    <i class="fa fa-arrow-up fa-lg"></i>
    <span>0%</span>
  </div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


  
  <script src="https://fastly.jsdelivr.net/npm/animejs@3.2.1/lib/anime.min.js" integrity="sha256-XL2inqUJaslATFnHdJOi9GfQ60on8Wx1C2H8DYiN1xY=" crossorigin="anonymous"></script>
  <script src="https://fastly.jsdelivr.net/npm/@next-theme/pjax@0.6.0/pjax.min.js" integrity="sha256-vxLn1tSKWD4dqbMRyv940UYw4sXgMtYcK6reefzZrao=" crossorigin="anonymous"></script>
<script src="/js/comments.js"></script><script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/sidebar.js"></script><script src="/js/next-boot.js"></script><script src="/js/pjax.js"></script>

  <script src="https://fastly.jsdelivr.net/npm/hexo-generator-searchdb@1.4.1/dist/search.js" integrity="sha256-1kfA5uHPf65M5cphT2dvymhkuyHPQp5A53EGZOnOLmc=" crossorigin="anonymous"></script>
<script src="/js/third-party/search/local-search.js"></script>







  




  

  <script class="next-config" data-name="enableMath" type="application/json">true</script><script class="next-config" data-name="mathjax" type="application/json">{"enable":true,"tags":"none","js":{"url":"https://fastly.jsdelivr.net/npm/mathjax@3.2.2/es5/tex-mml-chtml.js","integrity":"sha256-MASABpB4tYktI2Oitl4t+78w/lyA+D7b/s9GEP0JOGI="}}</script>
<script src="/js/third-party/math/mathjax.js"></script>


<script class="next-config" data-name="utterances" type="application/json">{"enable":true,"repo":"CSGrandeur/csgrandeur.github.io","issue_term":"pathname","theme":"github-light"}</script>
<script src="/js/third-party/comments/utterances.js"></script>

</body>
</html>
